1. Field of the Invention
This invention relates to technologies for authentication of electronic devices and systems. Specifically, this invention deals with electronic Physical Unclonable Function (PUF) technology.
2. Description of the Related Art
A Physical Unclonable Function (PUF) is a device or structure (physical, electronic, chemical, etc) that is easily implemented but difficult to counterfeit. A PUF could be an ink smear that is well documented and difficult to replicate. Some PUFs are implemented as drops of clear lacquer with multi-color glitter embedded (see Tuyls, Schrijenm, Geloven, Verhaegn, Wolters. “Read-Proof Hardware from Protective Coatings.” Cryptographic Hardware and Embedded Systems—CHES 2006, volume 4249 of Lecture Notes in Computer Science, pages 369-383. Springer, Oct. 10-13, 2006.). The glittered lacquer is easy to apply but it is obviously difficult to replicate any specific glitter pattern that is created.
In electronic systems a Physical Unclonable Function provides a secure method of deriving a unique code from electronic devices without embedding any memory cells or registers that can be counterfeited. PUF systems also provide a large number of challenge/response sets to make “guessing” the appropriate response difficult and impractical.
As shown in FIG. 1, the PUF system accepts a challenge variable of n-bits length and provides a response of m-bits length. The ideal Challenge/Response system uses large n and m and every response is a unique function of the challenge and the unique manufacturing variation of the integrated circuit. In classic symmetrical PUF systems (such as the example illustrated in FIG. 2), each bit of the response is produced from a separate test from all the other bits. The arbiter PUF elements shown in FIG. 2 produce a single bit result from the comparison of delay between the two arbitrated paths (the paths are arbitrated based on the challenge bits). In order to produce more output or response bits, more identical elements are composed. Based on the challenge, each test produces only one bit.
Those skilled in the art will appreciate that there are a few important terms that should be understood and defined when discussing PUF technology. These are Entropy, Stability, and Variance. These terms will be capitalized when used in this document to indicate that we are referring to the PUF characteristics.
Stability
First, the same challenge, applied to the same integrated circuit does not always result in the same response. In Symmetrical PUFs, a typical 128-bit challenge will produce a 128-bit response with 5-10 bits of difference resulting from each inquiry (not always the same bits changing, either). These 5-10 bits of uncertainty can be referred to as noise. Stability refers to the number of bits that remain constant when the same challenge is applied to the same PUF structure within the same integrated circuit. The inverse of the noise is the relative “Stability” of the PUF system.
Entropy
The second problem is “stuck bits.” Entropy describes the number of bits that change between differing challenges or between the same challenge on different integrated circuits. Bits that do not change are referred to as stuck bits. In many PUF systems, there are response bits that never change. These bits are really useless in determining the uniqueness or authenticity of a device. The percentage of bits that can be relied on (that change from challenge to challenge and from device to device) is referred to as Entropy. In other words, a 100-bit PUF response with 5 stuck bits has 95% Entropy.
Further, some bits may tend toward one value. That is, a bit may be a logical “1” 80% of the time. Although that bit is not “stuck” it does not exhibit perfect entropy (which would be a logical “1” 50% of the time and a logical “0” 50% of the time). A bit that exhibits one output 50% of the time has 100% bit-wise entropy. The bit described as having one value 20% of the time has a bit wise entropy of 40%.
Variation
Variation describes the difference in response between different integrated circuits when the same challenge is used. Cryptographically, 50% Variation is ideal. That is, when the same PUF system is implemented in two identical integrated circuits and the same challenge response is issued to each integrated circuit, half of the bits should be different between the two responses. For large digit numbers (say 128-bit or 256-bit numbers) there are a large number of terms that are 50% different from any given term. For example, there are 3.4×1038 possible numeric values for 128-bit binary numbers. For any given 128-bit binary number, v, there are 2.4×1027 other 128-bit binary numbers that exhibit a 50% variation from any given 128-bit value.
Challenge and Response
PUFs may be created to have multiple challenge-response pairs, whereby a challenge that sets a particular configuration controls the PUF's general behavior and the response is a quantifiable result of the PUF's specific behavior. An example analogy to this challenge-response pair may be giving someone a map with a marked path that they are to take from point A to point B, and the response would be the set of information describing the actual trip they took, such as how long they traveled, which side of the street they walked on, whether or not they stopped into a store along the way, etc. Two people given the same map (challenge) will inevitably have at least minor differences in their specific responses due to their own unique differences.
Programmable Logic Devices
Programmable Logic Devices (PLD) are integrated circuits that include memory, logic, and specialized functions that can be configured based on a specific configuration file. In this way, one designer may use a PLD to implement a microprocessor while another designer uses the same PLD component to implement a control system based on a complex state machine and yet another designer may implement an arithmetic unit, an image processing engine, a motor controller, or practically an infinite number of unique designs. Field Programmable Gate Arrays (FPGA) and Complex Programmable Logic Devices (CPLD) are the most common types of PLD currently in use. This application will refer to all of these types of devices as PLDs since the structures described may be implemented in any PLD with sufficient available resources.
In electronic systems, Physical Unclonable Functions have been developed based on the idea of creating circuits that are practically identical and comparing the output of these identical functions. Such functions are designed to be highly symmetrical, or equivalent. Theoretically, the only difference between the functions will be due to small differences caused by manufacturing tolerances. Since these minute differences are unique to every piece of silicon manufactured, the resulting system of nearly identical circuits will produce different results in every implementation. Symmetric PUF systems compare a large number of the identical structures. Each comparison results in a single bit binary response based on which structure or which electrical path was the fastest; that is, the response merely determines that a difference does in fact exist. Multiple instantiations are implemented in a design or configuration. The configuration is then applied to multiple integrated circuits so that a response difference from integrated circuit to integrated circuit is solely due to manufacturing differences, and the fact of such difference may be identified. By implementing a large number of supposedly identical instantiations, the resulting system allows any specific set or combinations of structures to be compared.
There are at least three problems associated with this approach. First, experimental data shows that some implementations do not yield a random response for each comparison of identical structures as would be expected. This is the Entropy problem. Comparing some of the instantiations (implemented in multiple integrated circuits) always yields the same response. As discussed above, these non-random responses may be referred to as “stuck bits”. If a 100 bit response contains 10 stuck bits, the response is said to have an Entropy (or a useful Entropy) of 90% (or 90 bits, in this case). For the purposes of authentication and cryptography, the strength of the PUF is only as good as the Entropy. The presence of stuck bits implies that the supposed identical structures are not all identical. For a PUF to be effective and useful in cryptographic and authentication applications, the Entropy must be high. A large number of significant bits are required.
Second, the single bit responses are not stable within a single integrated circuit. That is, when a number of structures are tested with multiple comparisons (that is the same test performed over and over on a single integrated circuit) some of the result bits change. These results are sometimes referred to as “noisy bits”. The effect may be referred to as response noise or as instability. The applicability of a PUF system for authentication and cryptographic uses is limited by this instability. For a PUF to be effective and useful, it must exhibit high Stability and highly stable responses.
Third, a single bit response provides only very limited information. There are no clues in the stuck bits detailing how badly the structures are mismatched; only that one structure is consistently slower than the other. There is also no information about the noisy bits that could be used to implement a correction.
Classical (Symmetrical) PUF Structures
The basic concept of PUF has been implemented in electronic devices (primarily Programmable Logic Devices, PLD) by comparing two seemingly identical circuits. Typically, the result of this comparison is generated by determining which (of the two identical circuits or paths) is faster. FIG. 2 shows a simplified version of the “Arbiter” PUF. In the arbiter PUF, each set of multiplexers creates a cell. The multiplexers are assumed to be identical and each cell is assumed to be identical to all other cells. A number of cells (typically 64 or 128) are combined to create a PUF Structure (the entire system illustrated in FIG. 2 represents a PUF Structure. In a typical PUF implementation, a number of supposedly identical PUF structures are implemented.
The PUF element shown in FIG. 2 measures the delay between the two paths specified by the challenge. The result only indicates that one path is longer than the other. This type of output is typical of many PUF designs and presents a number of challenges.
Identical Circuits
In the classic electronic PUFs, the first challenge is to make all test circuits as identical as possible so the test results are a function of the challenge and the manufacturing tolerance. As shown in FIG. 2, the arbiter PUF relies on differences in the routing paths through the multiplexers to determine the result. In order to create circuits that are as closely identical as possible a great deal of manual processes are required because the automated design tools are intended to optimize the circuits for speed and resource utilization, not for accuracy in producing identical cells or identical routing paths.
Additionally, modern PLDs are designed for optimized synchronous operation. That is, processes that utilize flip flops and registers clocked (or latched) by a common clock signal. PUFs are typically asynchronous circuits and the PLD structure is not designed to implement accurately identical asynchronous circuits. In fact, because of the layout of the PLD, routing resources in some areas of the chip are different from routing resources in other areas. These differences make it impossible to use these resources to implement structures identical to those implemented in other parts of the chip. (Reference: A. Maiti and P. Schaumont, “Improved RO PUF: An FPGA Friendly Secure Primitive”, Journal of Cryptography, 14 Oct. 2010).
A number of examples exist in previous art for using ring oscillators to detect Trojans, for authentication, and to produce unique integrated circuit fingerprints including: Devadas (U.S. Pat. No. 7,757,083), Trimberger (U.S. Pat. No. 7,941,673), and Jyothi (U.S. Patent Application Publication No. 2012/0278893). All of these are limited in areas that provide for effective correction of environmental effects. Ring oscillators are affected by the temperature of the silicon, the power supply voltage (Vcc), and the relative aging of the silicon. Systems that use a single bit result have no mathematical basis or tool for correcting the operation of the ring oscillator based on these environmental effects. Other patents completely ignore the fact that the ring oscillator frequency is affected by temperature, voltage, silicon age, and possibly other influences.
The Asymmetric Unclonable Function (AUF) of the present invention described herein addresses all of these problems.